'''
	递归问题的二大奥义：
		1. 基础条件，也就是最简单的返回结果的情况。
		2. 递归的调用自己，但是可以理解为其中的数据量在不断的减小，也就是在逐渐的靠近基础条件，这样才能返回结果。


	迷宫问题：该问题就是一个乌龟在地图中的搜索问题。可用递归的方式，也就是如果乌龟没有达到终止条件，那么它将用递归地方式走下去。
	具体如下：
		1. 从我们的起始位置，我们将首先尝试向北一格，然后从那里递归地尝试我们的程序。
		2. 如果我们通过尝试向北作为第一步没有成功，我们将向南一格，并递归地重复我的们程序。
		3. 如果向南也不行，那么我们将尝试向西一格，并递归地重复我们的程序。
		4. 如果北，南和西都没有成功，则应用程序从当前位置递归向东。
		5. 如果这些方向都没有成功，那么没有办法离开迷宫，我们失败。
	但是这样有个问题，向北走之后再向南走，再向北走。。。这样会陷入循环，所以考虑乌龟的行走的终止条件也就是基本情况如下：
		1. 乌龟撞到了墙。由于这一格被墙壁占据，不能进行进一步的探索。
		2. 乌龟找到一个已经探索过的格。我们不想继续从这个位置探索，否则会陷入循环。
		3. 我们发现了一个外边缘，没有被墙壁占据。换句话说，我们发现了迷宫的一个出口。
		4. 我们探索了一格在四个方向上都没有成功。这样就失败了
	这样思路就清晰了，这样我们首先需要根据txt创建一张地图类，这个地图存有乌龟的位置等等，然后再写一个搜索算法在地图中递归查找，直到找到出口为止。
	设计Maze类：
		- __init__` 读取迷宫的数据文件，初始化迷宫的内部表示，并找到乌龟的起始位置。
		- `drawMaze` 在屏幕上的一个窗口中绘制迷宫。
		- `updatePosition` 更新迷宫的内部表示，并更改窗口中乌龟的位置。
		- `isExit` 检查当前位置是否是迷宫的退出位置。
'''

import turtle

# 迷宫类
class Maze(object):
	# 读取迷宫数据，初始化迷宫内部，并找到海龟初始位置。
	def __init__(self, mazeFileName):
		rowsInMaze = 0							#初始化迷宫行数
		columnsInMaze = 0 						#初始化迷宫列数
		self.mazelist = []						#初始化迷宫列表
		mazeFile = open(mazeFileName, 'r')		#读取迷宫文件
		for line in mazeFile:					#按行读取
			rowList = [] 						#初始化行列表
			col = 0 							#初始化列
			# for ch in line[:-1]:				#这样会丢失最后一列
			for ch in line:						#按列读取
				rowList.append(ch)				#添加到行列表
				if ch == 'S':					#S为乌龟初始位置，即迷宫起点
					self.startRow = rowsInMaze	#乌龟初始行
					self.startCol = col 		#乌龟初始列
				col = col + 1 					#下一列
			rowsInMaze = rowsInMaze + 1 		#下一行
			self.mazelist.append(rowList)		#行列表添加到迷宫列表
			columnsInMaze = len(rowList) 		#获取迷宫总列数
		self.rowsInMaze = rowsInMaze 			#设置迷宫总行数
		self.columnsInMaze = columnsInMaze		#设置迷宫总列数
		self.xTranslate = -columnsInMaze/2 		#设置迷宫左上角的初始x坐标
		self.yTranslate = rowsInMaze/2 			#设置迷宫左上角的初始y坐标
		self.t = turtle.Turtle()				#创建一个海龟对象
		self.t.shape('turtle')					#给当前指示点设置样式(类似鼠标箭头)，海龟形状为参数指定的形状名，指定的形状名应存在于TurtleScreen的shape字典中。多边形的形状初始时有以下几种："arrow", "turtle", "circle", "square", "triangle", "classic"。
		self.wn = turtle.Screen()				#创建一个能在里面作图的窗口
		self.wn.setworldcoordinates(-columnsInMaze/2, -rowsInMaze/2, columnsInMaze/2, rowsInMaze/2)			#设置世界坐标系，原点在迷宫正中心。参数依次为画布左下角x轴坐标、左下角y轴坐标、右上角x轴坐标、右上角y轴坐标

	# 在屏幕上绘制迷宫
	def drawMaze(self):
		self.t.speed(20)						#绘图速度
		for y in range(self.rowsInMaze):		#按单元格依次循环迷宫
			for x in range(self.columnsInMaze):
				if self.mazelist[y][x] == OBSTACLE:	#如果迷宫列表的该位置为障碍物，则画方块
					self.drawCenteredBox(x + self.xTranslate, -y + self.yTranslate, 'orange')

	# 画方块
	def drawCenteredBox(self, x, y, color):
		self.t.up()								#画笔抬起
		self.t.goto(x - 0.5, y - 0.5)			#前往参数位置，此处0.5偏移量的作用是使乌龟的探索路线在单元格的正中心位置
		self.t.color(color)						#方块边框为橙色
		self.t.fillcolor('green')				#方块内填充绿色
		self.t.setheading(90)					#设置海龟的朝向，标准模式：0 - 东，90 - 北，180 - 西，270 - 南。logo模式：0 - 北，90 - 东，180 - 南，270 - 西。
		self.t.down()							#画笔落下
		self.t.begin_fill()						#开始填充
		for i in range(4):						#画方块边框
			self.t.forward(1)					#前进1个单位
			self.t.right(90)					#右转90度
		self.t.end_fill()						#结束填充

	# 移动海龟
	def moveTurtle(self, x, y):
		self.t.up()								#画笔抬起
		self.t.setheading(self.t.towards(x + self.xTranslate, -y + self.yTranslate))	#setheading()设置海龟朝向，towards()从海龟位置到由(x, y)，矢量或另一海龟位置连线的夹角。此数值依赖于海龟初始朝向，由"standard"、"world"或"logo" 模式设置所决定。
		self.t.goto(x + self.xTranslate, -y + self.yTranslate)	#前往目标位置

	# 画路径圆点
	def dropBreadcrumb(self, color):
		self.t.dot(color)						#dot(size=None, color)画路径圆点

	# 用以更新迷宫内的状态及在窗口中改变海龟位置，行列参数为乌龟的初始坐标。
	def updatePosition(self, row, col, val):
		self.mazelist[row][col] = val 			#设置该标记状态为当前单元格的值
		self.moveTurtle(col, row)				#移动海龟
		if val == PART_OF_PATH: 				#其中一条成功路径的圆点的颜色
			color = 'green'
		elif val == TRIED:						#尝试用的圆点的颜色
			color = 'black'
		elif val == DEAD_END:					#死胡同用的圆点的颜色
			color = 'red'
		self.dropBreadcrumb(color)				#画路径圆点并上色

	# 用以判断当前位置是否为出口。
	def isExit(self, row, col):
		return (row == 0 or row == self.rowsInMaze - 1 or col == 0 or col == self.columnsInMaze - 1)								#根据海龟位置是否在迷宫的4个边线位置判断

	# 返回键对应的值，影响searchFrom()中maze[startRow][startColumn]值的获取
	def __getitem__(self, key):
		return self.mazelist[key]

# 探索迷宫，注意此函数包括三个参数：一个迷宫对象、起始行、起始列。
def searchFrom(maze, startRow, startColumn):
	# 从初始位置开始尝试四个方向，直到找到出路。
	# 1. 遇到障碍
	if maze[startRow][startColumn] == OBSTACLE:
		return False
	# 2. 发现已经探索过的路径或死胡同
	if maze[startRow][startColumn] == TRIED or maze[startRow][startColumn]== DEAD_END:
		return False
	# 3. 发现出口
	if maze.isExit(startRow, startColumn):
		maze.updatePosition(startRow, startColumn, PART_OF_PATH)#显示出口位置，注释则不显示此点
		return True
	maze.updatePosition(startRow, startColumn, TRIED)#更新迷宫状态、设置海龟初始位置并开始尝试
	# 4. 依次尝试每个方向
	found = searchFrom(maze, startRow - 1, startColumn) or \
            searchFrom(maze, startRow + 1, startColumn) or \
            searchFrom(maze, startRow, startColumn - 1) or \
            searchFrom(maze, startRow, startColumn + 1)
	if found:													#找到出口
		maze.updatePosition(startRow, startColumn, PART_OF_PATH)#返回其中一条正确路径
	else:														#4个方向均是死胡同
		maze.updatePosition(startRow, startColumn, DEAD_END)
	return found

if __name__ == '__main__':
	PART_OF_PATH = 'O'			#部分路径
	TRIED = '.'					#尝试
	OBSTACLE = '+'				#障碍
	DEAD_END = '-'				#死胡同
	myMaze = Maze('maze.txt')	#实例化迷宫类，maze文件是使用“+”字符作为墙壁围出空心正方形空间，并用字母“S”来表示起始位置的迷宫文本文件。
	myMaze.drawMaze()			#在屏幕上绘制迷宫。
	searchFrom(myMaze, myMaze.startRow, myMaze.startCol)	#探索迷宫